package com.fengye.algorithms.leecode;

/**
 * 二分查找，然后插入
 * @Author fengye
 * @Date 2023/4/8 10:25
 **/
public class SearchInsert35 {
    public int searchInsert(int[] nums, int target) {
        int n = nums.length-1;
        if(nums[n] < target) {
            return n+1;
        } else if(nums[n] == target) {
            return n;
        }

        if(nums[0] >= target) {
            return 0;
        }
        int start = 0;
        int end = n;
        while(start < end) {
            int mid = (start + end) /2;
            if(nums[mid] == target) {
                return mid;
            } else if(nums[mid] > target) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return end;
    }
}
